Masala #0222

Sizga $N$ uzunlikda $S$ satr beriladi. Sizning vazifangiz ushbu satrdan yana bir nusxa tayyorlash, buning uchun sizga $M$ ta $L_i$ $(1 \le i \le M)$ satrchalar borligi aytiladi, bu satrchalar cheksiz ko`p. Siz $S$ satrni $M$ xil satrlar yordamida qayta yozishingiz kerak bunda $L_i$ satr bilan $L_j (1 \le i \le M, 1 \le j \le M,  i \space \text{va} \space j \space \text{bir xil bo`lishi mumkin})$ satrni faqat o`xshash harflarini ustma – ust qo`yish yordamida birlashtirishingiz yoki satrlarni ketma-ket joylashtirishingiz mumkin. Satrlarning tartibi buzilishiga ham ruxsat etilgan ammo satrlarni bo`laklash yoki teskarisiga o`girish mumkin emas.

Sizning vazifangiz $S$ satrdan eng kam nechta belgini qayta tiklay olmasligingizni aniqlash. Unutmang siz hosil qiladigan satr $N$ dan oshmasligi kerak!

Birinchi qatorda $N (1 \le N \le 3*10^5)$ butun son satr uzunligi.
Ikkinchi qatorda $S$ satr beriladi.
Uchinchi qatorda $M (1 \le M \le 5000)$ butun soni satrchalar soni
Keyingi $M$ ta qatorda $L_i (1 \le L_i \le 5000)$ satrchalar beriladi.
Barcha satrlardagi belgilar lotin kichik harflaridan iborat.

Yagona butun son masala yechimini chop eting!